from typing import List


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        if n == 0: return res
        
        nums = sorted(nums)  # 排序以保证重复的数组相邻，方便去重
        def dfs(path, used, depth):
            if depth == n:
                res.append(path[:])  # 全局只有一个 path 变量，因此这里需要拷贝
                return
            for i in range(n):  # 这里有个遍历的顺序，不会在撤销操作后重复搜索
                if i != 0 and not used[i-1] and nums[i-1] == nums[i]:  # 判断重复的条件
                    continue  # 跳过重复
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
                    dfs(path, used, depth+1)
                    used[i] = False  # 撤销操作，状态重置
                    path.pop()       # path 的变动只在尾部，因此为栈
        
        dfs(path=[], used=[False for _ in range(n)], depth=0)  # 全局只有一个 path 变量
        return res
